#ifndef __Utils_hpp__
#define __Utils_hpp__

#include "Platform.hpp"

namespace ge {

//----------------------------------------------------------------------------//
//  
//----------------------------------------------------------------------------//

template < class T >
inline const T& Min( const T& _a, const T& _b )
{
     return ( ( _a < _b ) ? ( _a ) : ( _b ) );    
}

template < class T >
inline const T& Max( const T& _a, const T& _b )
{
     return ( ( _a > _b ) ? ( _a ) : ( _b ) );    
}

template < class T >
inline void Swap( T& _a, T& _b )
{
     T _c = _a;
     _a = _b;
     _b = _c;
}

template < class T >
inline bool IsInRange( const T* _test, const T* _memory, uint _size )
{
     return _test >= _memory && _test < _memory + _size;
}

//----------------------------------------------------------------------------//
//  
//----------------------------------------------------------------------------//

template < class T > class Array;
template < class T > class List;

//----------------------------------------------------------------------------//
//  
//----------------------------------------------------------------------------//

template < class T >
class Less
{
 public:

     bool Eq( const T& _a, const T& _b ) const
     {
          return _a == _b;
     }

     bool Lt( const T& _a, const T& _b ) const
     {
          return _a < _b;
     }

     bool Le( const T& _a, const T& _b ) const
     {
          return _a <= _b;
     }
};

//----------------------------------------------------------------------------//
//  
//----------------------------------------------------------------------------//

template < class T >
class Greater
{
 public:

     bool Eq( const T& _a, const T& _b ) const
     {
          return _a == _b;
     }

     bool Lt( const T& _a, const T& _b ) const
     {
          return !(_a <= _b);
     }

     bool Le( const T& _a, const T& _b ) const
     {
          return !(_a < _b);
     }
};

//----------------------------------------------------------------------------//
//  
//----------------------------------------------------------------------------//

template < class T >
class QuickSort
{
 public:

     template< class C >
     static void Sort( T* _array, uint _count, const C& _cmp = C() )
     {
          if( _array && _count > 1 )
          {
               _Sort< C >( _array, _array + (_count - 1), _cmp );
          }
     }

 protected:

     template< class C >
     static void _Sort( T* _left, T* _right, const C& _cmp = C() )
     {
#     if 1
          register T& _pivot = _left[ ( _right - _left ) >> 1 ]; // Use central pivot
#     else
          register T& _pivot = _left[ ( _right - _left ) - Math::LimitRandom( _right - _left ) ]; // Use random pivot
#     endif

          register T* _l = _left;
          register T* _r = _right;

#     if 1 // Pre-setup ordering

          if( _cmp.Lt( *_r, *_l ) ) Swap( *_l, *_r ); // r < l : r..l 
          if( _cmp.Lt( *_r, _pivot ) ) Swap( _pivot, *_r ); // r < p : l..r..p
          if( _cmp.Lt( _pivot, *_l ) ) Swap( _pivot, *_l ); // p < l : p..l..r

#     endif

          while( _l <= _r )
          {
               for( ; _l < &_pivot && _cmp.Lt( *_l, _pivot ); ++ _l );
               for( ; _r > &_pivot && !_cmp.Le( *_r, _pivot ); -- _r );

               if( _l <= _r )
               {
                    if( _l != _r ) Swap( *_l, *_r );
                    -- _r;
                    ++ _l;
               }
          }

          if( _left <= _r && _r - _left ) _Sort< C >( _left, _r, _cmp );
          if( _l <= _right && _right - _l ) _Sort< C >( _l, _right, _cmp );
     }
};

//----------------------------------------------------------------------------//
//  
//----------------------------------------------------------------------------//

} // namespace ge

#endif//__Utils_hpp__
